
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * user:likai
 * Date:2022-11-18
 * Time:11:26
 */
class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
}
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list=new LinkedList<>();
        if(root==null){
            return list;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            List<Integer> cur=new LinkedList<>();
            int size=queue.size();
            for(int i=0;i<size;i++){
                TreeNode node=queue.poll();
                if(node.left!=null){
                    queue.add(node.left);
                }
                if(node.right!=null){
                    queue.add(node.right);
                }
                cur.add(node.val);
            }
            list.add(cur);
        }
        return list;
    }
    public List<List<Integer>> levelOrderBottom(TreeNode root) {

        Queue<TreeNode> queue=new LinkedList <>();
        Stack<List<Integer>> stack=new Stack<>();
        queue.add(root);
        List<List<Integer>> list =new LinkedList<>();
        if(root==null){
            return list;
        }
        while(!queue.isEmpty()){
            List<Integer> cur=new LinkedList<>();
            int size=queue.size();
            for(int i=0;i<size;i++){
                TreeNode node=queue.poll();
                if(node.left!=null){
                    queue.add(node.left);
                }
                if(node.right!=null){
                    queue.add(node.right);
                }
                cur.add(node.val);
            }
            stack.add(cur);
        }
        while(!stack.isEmpty()){
            list.add(stack.pop());
        }
        return list;
    }
}
public class Test {
    public static void main(String[] args) {
        List<Integer> list=new LinkedList<>();
        list.add(1);
        list.add(2);
        System.out.println(list);
        Queue<Integer> queue=new LinkedList<>();
    }
}
